package com.ycz.algorithm.utils.graph.adjacencymatrix;

import java.util.ArrayList;
import java.util.List;

/**
 * @author yancz
 * @ClassName AdjacencyMatrix
 * @description: // 基于邻接矩阵的图及其常用操作
 * @date 2025-01-09 09:55:27
 * @version: 1.0
 */
public class AdjacencyMatrix {

    List<Integer> vertexList; // 顶点集合{a,b,c,d}，元素代表顶点值，索引代表顶点的索引

    List<List<Integer>> adjMatrixList; // 邻接矩阵，外层list为行，内层list为列，元素为0或1，代表是否有边

    /*
     * @author yancz
     * @description // 构造方法
     * @date 2025/1/9 13:53
     * @param vertexes 顶点值数组
     * @param edges 边数组{(a,b),(c,d),(e,f)}，每个边是一个二元组(x,y)，代表顶点x和y之间的联系，这里的x和y不是顶点值，而是顶点值的索引
     * @return null
     */
    public AdjacencyMatrix(int[] vertexes, int[][] edges) {
        this.vertexList = new ArrayList<>();
        this.adjMatrixList = new ArrayList<>();
        // 添加顶点
        for (int val : vertexes) {
            addVertex(val);
        }
        // 添加边，每条边是一个二元组(x,y)，但是这里用索引(a,b)代替，a对应顶点值x的索引，b对应顶点值y的索引
        for (int[] e : edges) {
            addEdge(e[0], e[1]); // e[0]为第一个顶点的索引值，e[1]为第二个顶点的索引值
        }
    }

    // 获取顶点的数量
    public int getVertexCount() {
        return vertexList.size();
    }

    /*
     * @author yancz
     * @description // 添加顶点
     * @date 2025/1/9 10:11
     * @param val 顶点值
     * @return void
     */
    public void addVertex(int val) {
        int n = getVertexCount(); // 获取顶点数量
        vertexList.add(val); // 顶点列表中添加元素值
        // 若顶点数量为n，则矩阵为n * n
        List<Integer> newRow = new ArrayList<>(n);
        for (int j = 0; j < n; j++) { // 初始化行的所有元素值为0
            newRow.add(0);
        }
        adjMatrixList.add(newRow); // 邻接矩阵中添加新行
        for (List<Integer> row : adjMatrixList) { // 为每行添加新列，初始值为0
            row.add(0);
        }
    }

    /*
     * @author yancz
     * @description // 删除顶点
     * @date 2025/1/9 11:20
     * @param index 索引
     * @return void
     */
    public void removeVertex(int index) {
        if (index >= getVertexCount()) {
            throw new IndexOutOfBoundsException("索引越界！");
        }
        vertexList.remove(index); // 移除顶点列表中的值
        adjMatrixList.remove(index); // 移除邻接矩阵中的行
        for (List<Integer> row : adjMatrixList) {
            row.remove(index); // 移除邻接矩阵中的列
        }
    }

    /*
     * @author yancz
     * @description // 添加边
     * @date 2025/1/9 11:43
     * @param i 顶点1的索引
     * @param j 顶点2的索引
     * @return void
     */
    public void addEdge(int i, int j) {
        // 索引越界与相同视为无效边
        if (i < 0 || j < 0 || i >= getVertexCount() || j >= getVertexCount() || i == j) {
            throw new IndexOutOfBoundsException("索引越界！");
        }
        // 无向图中，邻接矩阵关于主对角线对称，满足(i,j) == (j,i)
        // 更新邻接矩阵的连接关系，有关系的将值设置为1，因为邻接矩阵是对称的，所以更新第i行j列的同时，也需要更新第j行i列
        adjMatrixList.get(i).set(j, 1);
        adjMatrixList.get(j).set(i, 1);
    }

    /*
     * @author yancz
     * @description // 删除边
     * @date 2025/1/9 15:24
     * @param i 顶点1的索引
     * @param j 顶点2的索引
     * @return void
     */
    public void removeEdge(int i, int j) {
        if (i < 0 || j < 0 || i >= getVertexCount() || j >= getVertexCount() || i == j) {
            throw new IndexOutOfBoundsException("索引越界！");
        }
        // 删除边即将顶点的邻接矩阵中对应位置的值设置为0
        adjMatrixList.get(i).set(j, 0);
        adjMatrixList.get(j).set(i, 0);
    }

    public void commonPrint() {
        System.out.println("顶点值列表：");
        for (int i : vertexList) {
            System.out.print(i + "\t");
        }
        System.out.println();
        System.out.println("-------------------");
        for (List<Integer> row : adjMatrixList) {
            for (int val : row) {
                System.out.print(val + "\t");
            }
            System.out.println();
        }
        System.out.println("-------------------");
    }

    public static void main(String[] args) {
        int[] vertexes = {1, 3, 2, 5, 4}; // 顶点数组
        int[][] edges = {
                {0, 1}, {0, 3},
                {1, 0}, {1, 2},
                {2, 1}, {2, 3}, {2, 4},
                {3, 0}, {3, 2}, {3, 4},
                {4, 2}, {4, 3}
        }; // 边数组
        AdjacencyMatrix adjacencyMatrix = new AdjacencyMatrix(vertexes, edges);
        adjacencyMatrix.commonPrint();
        // 删除顶点4，同时删除该顶点对应的行和列
        adjacencyMatrix.removeVertex(4); // 删除顶点4
        System.out.println("删除顶点4后：");
        adjacencyMatrix.commonPrint();
        // 再次添加顶点，同时需要添加边
        adjacencyMatrix.addVertex(4);
        adjacencyMatrix.addEdge(4, 2); // 添加边(4,2)
        adjacencyMatrix.addEdge(4, 3);   // 添加边(4,5)
        System.out.println("添加顶点4后：");
        adjacencyMatrix.commonPrint();
        adjacencyMatrix.addVertex(6);
        adjacencyMatrix.addEdge(5, 1); // 添加边(6,3)
        adjacencyMatrix.addEdge(5, 2); // 添加边(6,2)
        adjacencyMatrix.addEdge(5, 4); // 添加边(6,4)
        System.out.println("添加顶点6后：");
        adjacencyMatrix.commonPrint();

    }

}
